﻿using System.Collections.ObjectModel;
using System.Diagnostics;
using System.Windows;

using Game.Map;
using Game.Map.Extensions;
using Game.Objects;
using Game.Terrain;

namespace Game.PathFinder.Internal
{
    /// <summary>
    /// The A* algorithm is probably one of the most, if not the most 
    /// used pathfinding algorithm in game development today. What makes
    /// the A* algorithm so appealing is that it is guaranteed to find 
    /// the best path between any starting point and any ending point, 
    /// assuming, of course, that a path exists. Also, it's a relatively 
    /// efficient algorithm, which adds to its appeal.
    /// 
    /// A* will find a path between a starting node and an ending node. 
    /// 
    /// It accomplishes this by starting the search at the starting node 
    /// and then branching out to the surrounding nodes. It will begin at 
    /// the starting tile and then spread to the adjacent tiles. This 
    /// branching out to adjacent tiles continues until we reach the 
    /// destination node. However, before we start this branching search 
    /// technique, we need a way to keep track of which tiles need to 
    /// be searched. This is typically called the open list when using 
    /// the A* algorithm. We begin with just one node in the open list. 
    /// This is the starting node. We will add more nodes to the open 
    /// list later.
    /// </summary>
    class AStarFinder : Finder
    {
        readonly IGameMap _gameMap;
        readonly NodeCollection _openList;
        readonly NodeCollection _closedList;
        readonly IMapField _startField;
        readonly IMapField _goalField;
        
        public AStarFinder(IGameMap gameMap, IMapField startField, IMapField goalField)
        {
            _gameMap = gameMap;
            _startField = startField;
            _goalField = goalField;
            _openList = new NodeCollection();
            _closedList = new NodeCollection();
        }
        
        public IGameMap GameMap
        {
            get { return _gameMap; }
        }
        
        public IMapField StartField
        {
            get { return _startField; }
        }
        
        public IMapField GoalField
        {
            get { return _goalField; }
        }
        
        /// <summary>
        /// add the starting node to the open list
        /// while the open list is not empty
        /// {
        ///     current node=node from open list with the lowest cost
        ///     if current node = goal node then
        ///         path complete
        ///     else
        ///         move current node to the closed list
        ///         examine each node adjacent to the current node
        ///         for each adjacent node
        ///             if it isn't on the open list
        ///                 and isn't on the closed list
        ///                     and it isn't an obstacle then
        ///                         move it to open list and calculate cost
        /// }
        /// </summary>
        public override GamePath Find()
        {
            var start = new Node(_gameMap, null, _startField.Point, this, 0);
            var goal = new Node(
                _gameMap, null, _goalField.Point, 
                this, _goalField.TerrianX().TerrainCost);
            var vehicle = _startField.VehicleX().Vehicle;
            
            if (start == goal)
            {
                return new GamePath(start.Point, goal.Point);
            }
            
            // add the starting node to the open list
            _openList.Add(start);

            Node destinationNode;
            
            // while the open list is not empty
            while(_openList.Count > 0)
            {
                // current node=node from open list with the lowest cost
                Node currentNode = _openList.First;
                
                // if current node = goal node then
                if (currentNode == goal)
                {
                    // path complete
                    break;
                }
                
                // move current node to the closed list
                _closedList.Add(currentNode);
                _openList.Remove(currentNode);
                
                // examine each node adjacent to the current node
                // for each adjacent node
                var adjacentPoints = MapUtil.GetAdjacentFields(
                    _gameMap, currentNode.Point);
                foreach (var adjacentField in adjacentPoints) 
                {
                    var adjacentNode = new Node(_gameMap, 
                        currentNode, adjacentField.Point, this, 
                        adjacentField.TerrianX().TerrainCost );
                    
                    // if it isn't on the open list
                    if (_openList.ContainsNode(adjacentNode))
                    {
                        continue;
                    }
                    
                    // and isn't on the closed list
                    if (_closedList.ContainsNode(adjacentNode))
                    {
                        continue;
                    }
                    
                    // and it isn't an obstacle then
                    Debug.Assert(vehicle != null, "vehicle != null");
                    ReadOnlyTerrainAccess access = vehicle.TerrainAccess;
                    if (!access.IsAccessible(adjacentField.TerrianX().TerrainType))
                    {
                        continue;
                    }

                    var obj = adjacentField.ObjectX().GameObject;
                    if (obj != null && obj.Building != null)
                    {
                        continue;
                    }

                    // Check for success
                    if (adjacentNode.Point == goal.Point)
                    {
                        destinationNode = adjacentNode;
                        goto success;
                    }
                    
                    if (adjacentField.VehicleX().Vehicle != null)
                    {
                        continue;
                    }
                    
                    // move it to open list and calculate cost
                    _openList.Add(adjacentNode);
                }
            }
            
            return null;

        success:
            // Build the path
            var collection = new Collection<Point>();
            Node cursor = destinationNode;
            while(cursor != null)
            {
                collection.Insert(0, cursor.Point);
                cursor = cursor.Parent;
            }
            
            return new GamePath(collection);
        }
        
        
    }
    
}
